CS 5010: Problem Set 04: Working with Lists

Out: Monday, October 3, 2016

Due: Monday, October 10, 2016 at 600pm local time

The goal of this problem set is to give you practice designing functions that deal with lists, and to give you practice using the System Design Recipe.

Use the HtDP Intermediate Student Language to solve the problems.

For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line

(require "extras.rkt")

(provide function)

Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS04.

Note: For all universe programs, you may assume that the mouse is never dragged or moved outside of the canvas. Once the mouse enters the canvas, if the mouse ever leaves the canvas, then the behavior of your system is unspecified.

1. (screensaver-3). Your boss has decided that your screensaver needs more features.
   1. The new screensaver will display a list of circles.
   2. Initially, there are no circles. Hitting the "n" key adds a new circle, at the center of the canvas, at rest (velocity is 0).
   3. When a circle is selected, the arrow keys increase the velocity of the circle in the specified direction (up, down, left, or right). Each push of the arrow key increases the velocity by 2 pixels/tick. When the circle is deselected, the circle resumes its motion with the new velocity. Each circle displays its velocity, as in the past.
   4. When a circle is selected, the "d" key drops a pen down. When the pen is down, the circle records on the screen a dot marking its center at each tick. The dot is displayed as a solid black circle of radius 1. No marks are made during a drag.
   5. When a circle is selected, the "u" key lifts the pen up. When the pen is up, the circle does not leave a track on the screen.
   6. When a circle is selected, the "e" key erases all the marks made by that circle.

   Here's a demo:

   You are to deliver a file named screensaver-3.rkt that provides all the functions of screensaver-2.rkt (except for world-circ1 and world-circ2), plus the following:

   ;; world-circles : WorldState -> ListOfCircle
   ;; RETURNS: the specified attribute of the WorldState
   ;; NOTE: if these are part of the world struct, you don't need to
   ;; write any deliverables for these functions.
   
   ;; circle-after-key-event : Circle KeyEvent -> Circle
   ;; RETURNS: the state of the circle that should follow the given
   ;; circle after the given key event
   
   ;; circle-pen-down? : Circle -> Boolean
   ;; RETURNS: true if the pen in the given circle is down
     

   In addition, you must turn in a file containing the call graph for your program. This file must show which functions call which, so we (and you) can see the overall structure of your program and find all the recursive calls. You may turn this in as a text file, pdf, jpg, or Racket file. Call your file call-tree with an appropriate suffix, and bring a paper copy to your codewalk.

   Remember to use the principle that Program Structure Follows Data Structure, illustrated in Lesson 3.4, to organize your program.

2. Professor Felleisen and Professor Shivers each keep their class lists on slips of paper, one student on each slip. Professor Felleisen keeps his list on slips of yellow paper. Professor Shivers keeps his list on slips of blue paper.

   Unfortunately, both professors are sloppy record-keepers. Sometimes they have more than one slip for the same student. Sometimes they record the student names first-name first; sometimes they record the names last-name first.

   One day, Professor Felleisen was walking up the stairs in WVH, talking to one of his graduate students. At the same time, Professor Shivers was walking down the stairs, all the time talking to one of his graduate students. They collided, and dropped all the slips containing their class lists on the stairs, where they got all mixed up.

   Your job is to clean up this mess. Deliver a file named class-lists.rkt that provides the following functions:

   felleisen-roster : ListOfSlip -> ListOfSlip
   GIVEN: a list of slips
   RETURNS: a list of slips containing all the students in Professor
   Felleisen's class, without duplication.
   
   shivers-roster: ListOfSlip -> ListOfSlip
   GIVEN: a list of slips
   RETURNS: a list of slips containing all the students in Professor
   Shivers' class, without duplication.
   
   possible-roster? : ListOfSlip -> Boolean
   GIVEN: a list of slips
   RETURNS: true iff all the slips in the list are the same color,
                     and no student is represented twice.
   
   acceptable-felleisen-answer? : ListOfSlip ListOfSlip -> Boolean
   GIVEN: two lists of slips, lst1 and lst2
   RETURNS: true iff every student on a yellow slip in lst1 appears once
   and only once in lst2.
   EXAMPLES:
     Let lst1 = (list
                 (make-slip "yellow" "Wang" "Xi")
                 (make-slip "blue" "Jones" "Tom")
                 (make-slip "yellow" "Xi" "Wang")
                 (make-slip "yellow" "Shriram" "K."))
   
   This list contains two of Professor Felleisen's students: Wang Xi (or
   maybe Xi Wang), and Shriram K.  Therefore the following are acceptable
   answers and should return true when given to acceptable-felleisen-answer? 
   
   (list
    (make-slip "yellow" "Wang" "Xi")
    (make-slip "yellow" "Shriram" "K."))
   
   (list
    (make-slip "yellow" "Shriram" "K.")
    (make-slip "yellow" "Wang" "Xi"))
   
   (list
    (make-slip "yellow" "Shriram" "K.")
    (make-slip "yellow" "Xi" "Wang"))
   
   (list
    (make-slip "yellow" "K." "Shriram")
    (make-slip "yellow" "Xi" "Wang"))
   
   Any answer with a blue slip, or any answer that includes both Xi Wang
   and Wang Xi, or any answer that does not include both Xi Wang and
   Shriram K, is not acceptable.
   

   Here is the beginning of the data definition for ListOfSlip:

   (define-struct slip (color name1 name2))
   A Slip is a (make-slip Color String String)
   
   A Color is one of
   -- "yellow"
   -- "blue"
   

   As mentioned before, the professors are confused about first names and last names, so (make-slip "yellow" "Wang" "Xi") and (make-slip "yellow" "Xi" "Wang") represent the same student in Professor Felleisen's class. The phrase "without duplication" in the purpose statements above means that your function should return a list in which this student is represented only once.

   Be sure to finish the data definitions I've started above, and to provide make-slip, slip-color, slip-name1 and slip-name2.